The algorithm which the invention is intended to implement is known in the art and was described in: R. V. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public Key Cryptosystems", Comm. ACM, vol. 21, pp. 120-126, 1978. Its implementation involves exponentiation and modulo reduction, as indicated by the formula:
MEmodN=C, and also many other large operand algorithms suggested in the art and by standardization organizations, which necessitate conventional and modular arithmetic. The arithmetic process involved is modulo multiplication, which requires addition, subtraction and shifting.
FIG. 1, attached hereto, illustrates the flow chart of the algorithm for operands which are no larger than the registers. Therein M indicates the message, N the modulo, and E the exponentiation key. The implementation of the algorithm essentially requires six registers. Since the data block, the exponentiation and modulo reduction whereof are to be carried out, may comprise a large number of bits, e.g. several hundreds, the microcircuits required to implement it in the way practiced in the prior art may become quite expensive, because the registers become accordingly larger and require relatively large silicon surfaces, the cost of which, as well known to persons skilled in the art, increases dramatically with the increase in size.
The circuit also enables the encryption and decryption of messages whose size is larger than that of the registers. This is to be done by an interleaved Montgomery reduction, as known in the art [P. L. Montgomery, "Modular Multiplication Without Trial Division", Mathematics of Computation, vol. 44, pp. 519-521, 1985.], and/or by utilizing a novel approach to processing of double precision operands by single precision hardware. In particular, the circuit naturally enables the calculation of J=-N.sup.-1 mod 2.sup.L, where N is the modulus and L is the word size. The value of J is necessary for divisionless modular exponentiation as known to experts in the art. Also in particular, the circuit enables a double precision division.